/**
 * 152. Maximum Product Subarray 最大乘积子数组
 * https://leetcode.com/problems/maximum-product-subarray/
 */
class MaximumProductSubarray {
    /**
     * 方法：动态规划求解最大乘积子数组
     *       维护两个变量fMax和fMin分别记录以当前位置结尾的子数组的最大乘积和最小乘积
     *       对于每个数x:
     *       - 新的最大乘积可能是fMax*x、fMin*x或x本身
     *       - 新的最小乘积可能是fMax*x、fMin*x或x本身
     *       - 更新全局最大值ans
     *
     * Args:
     *      nums: int[] - 输入的整数数组
     *
     * Returns:
     *      int: 连续子数组的最大乘积
     *
     * Time: O(n) - n为数组长度，需要遍历一次数组
     *
     * Space: O(1) - 只需要常数空间存储变量
     */
    public int maxProduct(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int fMax = 1;
        int fMin = 1;
        for(int x : nums){
            int mx = fMax;
            fMax = Math.max(Math.max(fMax * x, fMin * x), x);
            fMin = Math.min(Math.min(mx * x, fMin * x), x);
            ans = Math.max(ans, fMax);
        }
        return ans;
    }
}